1. Field of the Invention
The invention relates to methods, apparatus, and systems utilizing soft output Viterbi algorithms in a digital channel decoder. More specifically the invention relates to methods, apparatus, and systems for determining 1T path equivalency information from an nT implementation of a soft output Viterbi decoder.
2. Discussion of Related Art
In most present digital communication channels, information is encoded in a manner to improve reliability of the transmitted information in the presence of imperfect or noisy communication channels. Exemplary of such communication channels are digital voice and data communication channels utilizing, for example, RF modulation for transmission of digital data. Another exemplary application of such digital channels are storage devices with read/write channels that write digital information using optical or magnetic modulation techniques for later recovery through a corresponding read channel.
One common decoding algorithm is known as the Viterbi algorithm. Broadly speaking, the Viterbi algorithm is a dynamic programming algorithm that determines the most likely sequence of states that result in a sequence of observed events in the received signal. This most likely sequence of states then defines the decoded symbol based on the path of most likely values of the observed events. In general, the Viterbi decoder determines the most likely transmitted sequence of encoded data bits that may be the underlying cause of an observed sequence of sensed events. In other words, the Viterbi decoder determines the most likely sequence of encoded data bits represented by a received sequence of modulated events.
Improvements to the Viterbi algorithm known as the soft output Viterbi algorithm (“SOVA”) improve upon prior algorithms by including reliability or probability information for each decoded bit of the decoded symbol and, by accumulating this bit-wise reliability or probability information, a reliability or probability value associated with the most likely decoded symbol can be generated. Basic concepts of the SOVA techniques and common applications thereof are well known to those of ordinary skill in the art and are notoriously disclosed by Hagenauer and Hoeher in 1989 in the paper entitled “A Viterbi Algorithm With Soft-Decision Outputs and its Applications” (IEEE 1989 and incorporated herein by reference). The SOVA algorithms utilize branch metric information associated with each branch from the first state to each of two subsequent, potential follow-on states to determine the most likely branch for a next sensed event. Hagenauer and Hoeher first taught that the difference in accumulated branch metric information between the most likely and second most likely paths of the Viterbi detector in response to each sensed event is a useful approximation of the log-likelihood ratio (“LLR”) used in the SOVA techniques to determine reliability of the surviving path (e.g., reliability of the decoded bit). This state metric difference (“SMD”) is therefore used to implement SOVA techniques in present Viterbi decoders.
Those of ordinary skill in the art will readily recognize that the state metric and branch metric information discussed herein is also more simply referred to herein as “metric information” or as “path metric information”.
In earlier Viterbi algorithm state machines, each bit or received event is received or sensed on a corresponding cycle of an applicable clock signal. The clock signal generally cause a transition of the state machine to determine the most likely bit value for the sensed event based on past sensed events and corresponding branch metric information. In other words, each clock cycle of the Viterbi algorithm state machine corresponds to decoding of one bit of the encoded symbol. Branch metric information is therefore encoded in association with each possible transition corresponding to each clock cycle operable in the Viterbi algorithm state machine. Such Viterbi decoders in which each clock pulse corresponds to processing of one
As the data rate (e.g., “baud” rate) for application of Viterbi decoders has increased, many present day decoders utilized a “2T” decoder structure such that each clock cycle decodes a sequence of two consecutive bits of the encoded symbol. Such a 2T decoder implementation has four possible transitions from a current state to a next state based upon a sensed event representation of two encoded bits. Thus the clock rate of the Viterbi decoder state machine is typically half that of the data/baud rate of transmitted information. More generally, modern Viterbi decoders may utilize a clock rate whose frequency is an integer fraction of the corresponding data rate. In other words, an “nT” Viterbi decoder may use a clock that has a frequency of 1/n times the data rate. Thus each clock pulse in an nT Viterbi decoder represents n bits of the symbol to be decoded. An nT Viterbi decoder is therefore operable in accordance with an nT state machine.
The Sibling patent application teaches methods and apparatus for generating 1T path metric information from an nT Viterbi decoder design. A paper by Yeo et al entitled “500 Mb/s Soft Output Viterbi Decoder” (ESSCIRC 2002; pp. 523-526—hereinafter “Yeo” and hereby incorporated by reference) presents a 1T SOVA decoder design. The 1T SOVA design of Yeo includes a path equivalency detector (“PED”) component that identifies dissimilarities of decisions feeding into each decision node. As known to those of ordinary skill in the art, the PED generates a logic high signal if the competing bits applied to its inputs are the same and generates a logic low signal if the applied bits are different. The PED output signals are applied to control update of the LLR determination at each clock. However, to update the appropriate LLR values in an nT Viterbi design it is necessary to know the equivalency bit at each decision node (i.e., at each 1T decision node) rather than just at each clock pulse (i.e., at each nT clock pulse).
It is evident from the above discussion that an ongoing need exists to usefully apply SOVA techniques in an nT state machine implementation of a Viterbi decoder to provide 1T path equivalency information for the nT SOVA implementation.